/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.fjala.softure.tree.linkedTree;

import java.util.*;
import org.fjala.softure.tree.Node;
import org.fjala.softure.tree.Tree;

/**
 * Linked tree implementation of the <tt>Tree</tt> interface.  Implements all
 * optional tree operations, and permits all elements (including
 * <tt>null</tt>).
 * 
 * @author Luis Aguirre.
 * @author Juan Carlos Quispe.
 */
public class LinkedBynaryTree<E> implements Tree<E>{
    
    private LinkedBinaryNode<E> root;

    @Override
    public void replace(E oldElement, E newElement) {
        replace(root, newElement, oldElement);
        LinkedList l;
    }

    @Override
    public Node<E> getRoot() {
        return root;
    }

    @Override
    public boolean add(Node<E> parent, E element) {
        if (parent instanceof LinkedBinaryNode) {
            search(root, (LinkedBinaryNode<E>)parent).addChild(new LinkedBinaryNode(element, null));
            return true;
        }
        
        return false;
    }

    @Override
    public int size() {
        return size(root);
    }

    @Override
    public boolean isEmpty() {
        return root == null;
    }

    @Override
    public boolean contains(Object o) {
        return search(root, (E)o) != null;
    }

    @Override
    public Iterator<E> iterator() {
        return toList().iterator();
    }

    @Override
    public Object[] toArray() {
        return toList().toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return toList().toArray(a);
    }

    @Override
    public boolean add(E e) {
        if (root == null) {
            root = new LinkedBinaryNode<E>(e, null);
        } else {
            LinkedBinaryNode<E> node = new LinkedBinaryNode<E>(e, null);
            root.addChild(node);
        }
        return true;
    }

    @Override
    public boolean remove(Object o) {
        if (o.equals(root.getData())) {
            root = null;
            return true;
        }
        return remove(root, o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o: c) {
            if(!contains(o)) {
                return false;
            }
        }
        
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        for (E o: c ) {
            add(o);
        }
        
        return true;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        for(Object o: c) {
            if (remove(o) == false) {
                return false;
            }
        }
        
        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
	Iterator<E> e = iterator();
        
	while (e.hasNext()) {
	    if (!c.contains(e.next())) {
		e.remove();
		modified = true;
	    }
	}
	return modified;
    }

    @Override
    public void clear() {
        root = null;
    }
    
    /**
     * Returns the size of a given node
     * 
     * @param node Node to get size of
     * @return size of a given node
     */
    private int size(LinkedBinaryNode<E> node) {
        if(node != null) {
            return 0;
        } else {
            int leftCount = size(node.getLeft());
            int rightCount = size(node.getRight());
            
            return leftCount + rightCount + 1;
        }
    }
    
    /**
     * Searches for a node in a node
     * 
     * @param node Node were the search will take place
     * @param toFind Node to search
     * @return a node. If not found returns null
     */
    private Node search(LinkedBinaryNode<E> node, LinkedBinaryNode<E> toFind) {
        Node ans = null;
        
        if (node != null) {
            if (toFind.equals(node.getLeft())) {
                ans = node.getLeft();
            } else if (toFind.equals(node.getRight())) {
                ans = node.getRight();
            }
            else {
                ans = search(node.getLeft(), toFind);
                if(ans == null) {
                    ans = search(node.getRight(), toFind);
                }
            }
                
        }
        
        return ans;
    }
    
    /**
     * Searches for a node given  node and an element
     * 
     * @param node Node were we will look with
     * @param toFind Element to find
     * @return a LinkedBinaryNode . If not found returns null
     */
    private LinkedBinaryNode<E> search(LinkedBinaryNode<E> node, E toFind) {
        LinkedBinaryNode<E> ans = null;
        
        if (node != null) {
            if (node.getLeft() != null && node.getLeft().getData().equals(toFind)) {
                ans = node.getLeft();
            } else if (node.getRight() != null && node.getRight().getData().equals(toFind)) {
                ans = node.getRight();
            }
            else {
                ans = search(node.getLeft(), toFind);
                if (ans == null) {
                    ans = search(node.getRight(), toFind);
                }
            }
        }
        
        return ans;
    }
    
    /**
     * Replaces a value of a node in a given node
     * 
     * @param node Node were the replace will take place
     * @param newValue New value to replace with
     * @param toReplace Value to be replaced
     */
    private void replace(LinkedBinaryNode<E> node, E newValue, E toReplace) {
        if (node != null) {
            if (node.getData() != null) {
                if (node.getData().equals(toReplace)) {
                    node.setData(newValue);
                }
                if (node.getData().equals(toReplace)) {
                    node.setData(newValue);
                }
            }
            
            replace(node.getLeft(), newValue, toReplace);
            replace(node.getRight(), newValue, toReplace);
        }
    }
    
    /**
     * Returns a list with all the elements of the tree
     * 
     * @return a list with all the elements of the tree
     */
    public List<E> toList() {
        List<E> ans = new ArrayList<E>();
        ans.add(root.getData());
        ans.addAll(toList(root));
        return ans;
    }

    /**
     * Returns a list with all the elements of a node
     * 
     * @param node Node were elements will be taken
     * @return a list with all the elements of a node
     */
    private List<E> toList(LinkedBinaryNode<E> node) {
        List<E> ans = new ArrayList<E>();
        
        if (node != null) {
            if (node.getLeft() != null) {
                ans.add(node.getLeft().getData());
            }
            if (node.getRight() != null) {
                ans.add(node.getRight().getData());
            }
            ans.addAll(toList(node.getLeft()));
            ans.addAll(toList(node.getRight()));
        }
        
        return ans;
    }

    /**
     * Removes an object from a node
     * 
     * @param node Node were the object will be removed
     * @param toFind Object to remove
     * @return True if the object was found. If not returns false.
     */
    private boolean remove(LinkedBinaryNode node, Object toFind) {
        if (node != null) {
            if (node.getLeft() != null && toFind.equals(node.getLeft().getData())) {
                node.setLeft(null);
                return true;
            } else if (node.getRight() != null && toFind.equals(node.getRight().getData())) { 
                node.setRight(null);
                return true;
            } else {
                boolean aux = remove(node.getLeft(), toFind);
                if (aux == false) {
                    aux = remove(node.getRight(), toFind);
                }
                return aux;

            }
        }
        
        return false;
    }
}